1. Field of the Invention
Aspects of the invention relate generally to routing data in computer networks. More particularly, aspects are directed to deadlock prevention in computer networks regardless of system configuration.
2. Description of Related Art
In many communication networks, multiple processors are often employed. The processors may be arranged in different configurations. For instance, an array of processors may be configured in a mesh or torus architecture. The array may also be interconnected to other arrays in different networks.
Various routing schemes, including flow control, have been employed to pass data between components within such communication networks. However, some communication networks use flow control mechanisms that can stall traffic on a link into a switch of a node until buffer space or other resources become available. Blockage on an output link of a network node may propagate backwards across the switch and stall its input links that are trying to route the stalled output.
A condition known as “deadlock” can arise in which a stalled link is indirectly dependent upon itself. Deadlock is a serious condition causing loss of data errors and which may require a network restart to correct. Previously, different techniques have been employed to combat deadlock. Unfortunately, such techniques may fail in different situations.
For instance, a “turn model” may require specific restrictions for each type of network topology. The turn model may fail when the network is missing a link or switch and no longer provides a complete topology. In “up*/down*” routing, an arbitrary network is covered by a spanning tree. Routes are constrained to flow in certain directions; however this may lead to link load imbalance near the root of the spanning tree and may also require a network restart when a link or switch goes down. In “folded Clos” or “fat tree” type networks, deadlock is addressed by imposing route restrictions that may be unduly limiting.